package com.topcoder.srm522;

public class RowAndCoins {
	public String getWinner(String cells) {
		int n = cells.length();
		boolean[] aWin = new boolean[1<<n];
		boolean[] bWin = new boolean[1<<n];
		
		for (int set=1; set<(1<<n); set++) {
			if (Integer.bitCount(set) == 1) {
				for (int i=0; i<n; i++) {
					if ((set & (1<<i)) > 0) {
						if (cells.charAt(i) == 'A') {
							aWin[set] = true;
						}
						else {
							bWin[set] = true;
						}
					}
				}
			}
			else {
				for (int start=0; start<n; start++) {
					for (int len=1; start+len<=n; len++) {
						int mask = ((1<<len) - 1) << start;
						if ((set & mask) == mask && set != mask) {
							int dest = set ^ mask;
							if (!aWin[dest]) bWin[set] = true;
							if (!bWin[dest]) aWin[set] = true;
						}
					}
				}
			}
		}
		
		return aWin[(1<<n) - 1]? "Alice" : "Bob";
	}
}
